МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” / Кафедра ЕОМ Розрахунковова робота на тему "Динамічні структури даних" з дисципліни "Обчислювальний практикум"  Зміст Зміст……………………………………………………………………………………...2 Завдання 1. АТД «СТЕК»……………………………………………………………....3 Умова задачі…………………………………………………………………3 Аналіз завдання………………………………………………………….…..3 Проектування алгоритму………………………………………………...….3 Програмна реалізація………………………………………………………..5 Результат виконання програми……………………………………………..8 Завдання 2. АТД «ЧЕРГА»……………………………………………………………..9 Умова задачі…………………………………………………………………9 Аналіз завдання………………………………………………………….…..9 Проектування алгоритму………………………………………………......10 Програмна реалізація………………………………………………………10 Результат виконання програми……………………………………………11 Завдання 3. АТД «СПИСОК»…………………………………………………………13 3.1 Умова задачі………………………………………………………………..13 3.2 Аналіз завдання………………………………………………………….…13 3.3 Проектування алгоритму………………………………………………......14 3.4 Програмна реалізація………………………………………………………14 3.5 Результат виконання програми……………………………………………16 Завдання 4. АТД «ДЕРЕВО»…………………………………………………………..17 Умова задачі………………………………………………………………..17 Аналіз завдання………………………………………………………….…17 Проектування алгоритму………………………………………………......18 Програмна реалізація………………………………………………………18 Результат виконання програми……………………………………………24 Висновок. …………………………………………………………………………….....24  Завдання 1 1.1 Умова задачі Застосування АТД "СТЕК" до розв’язання прикладних задач Обчислити вираз, представлений в постфіксній формі запису. Аналіз завдання Зворо́тній по́льський за́пис (зворотний бездужковий запис, постфіксна нотація, польський інверсний запис (ПОЛІЗ), англ. RPN — Reverse Polish Notation) — форма запису математичних виразів, в якій знаки операцій розташовано після операндів. Розташування знаків операцій перед операндами використовує польська нотація. Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов). Основні операції для роботи зі стеком: push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow) pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (англ. stack underflow) Додаткові операції (присутні не у всіх реалізаціях стеку): isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній. isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе. clear: звільнити стек (видалити усі елементи). top: отримати верхній елемент (без виштовхування). size: отримати розмір (кількість елементів) стека. swap: поміняти два верхніх елементи місцями. Проектування алгоритму На рис.1. зображено алгоритм обчислення виразу, представленого в постфіксній формі запису. Для всіх символів робимо наступне: Якщо Аі число, то вкласти його у стек; Якщо Аі оператор, то: Витягуємо із стеку два числа; Виконуємо дію із числами і результат вкладаємо в стек; Якщо Аі є функцією то: Витягуємо із стеку одне число; Визначаємо значення функції із відповідним аргументом та поміщаємо результат у стек; В кінці роботи в стеку знаходитиметься результат виразу. / Рис 1. Алгоритм обчислення в постфіксній формі Програмна реалізація #include <iostream> #include <locale> #include <string> #include <cmath> using namespace st...